package sliding_window;

/**
 * @Description 剑指 Offer II 009. 乘积小于 K 的子数组
 * @Author Firenut
 * @Date 2023-04-16 22:07
 */
public class II009_numSubarrayProductLessThanK {
    // 法2: 滑动窗口 (https://leetcode.cn/problems/ZVAVXX/solution/jian-zhi-offerii009cheng-ji-xiao-yu-kde-q158e/)
    // 每次固定右指针,满足total<k条件下的最左边指针即left
    // 右指针移动一次,得到的满足条件的新增子数组个数: j-i+1 (必须包含nums[j])
    // 这些子数组分别是:
    //   nums[j]、(nums[j],nums[j-1])、(nums[j],nums[j-1],nums[j-2]) ... (nums[j],nums[j-1],nums[j-2],... nums[i])
    // 时间复杂度: O(n)
    public int numSubarrayProductLessThanKV1(int[] nums, int k) {
        int ans = 0, total = 1, left = 0;
        for (int right = 0; right < nums.length; right++) {
            total *= nums[right];
            while (left <= right && total >= k) {
                // total 大于k,需要移动左指针继续判断
                total /= nums[left++];
            }
            if (left <= right) {
                // 如果 nums[right] > k,会出现left>right的情况
                ans += (right - left + 1);
            }
        }
        return ans;
    }

    // 法1: 暴力法
    // 时间复杂度:O(n^2)
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        int ans = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] < k) {
                ans++;
            }
            int mutipart = nums[i];
            for (int j = i + 1; j < nums.length; j++) {
                mutipart *= nums[j];
                if (mutipart < k) {
                    ans++;
                } else break;
            }
        }
        return ans;
    }
}
